package com.zlk.algorithm.algorithm.dynamicPlan.PartitionedKnapsack074;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

// 从栈中取出K个硬币的最大面值和
// 一张桌子上总共有 n 个硬币 栈 。每个栈有 正整数 个带面值的硬币
// 每一次操作中，你可以从任意一个栈的 顶部 取出 1 个硬币，从栈中移除它，并放入你的钱包里
// 给你一个列表 piles ，其中 piles[i] 是一个整数数组
// 分别表示第 i 个栈里 从顶到底 的硬币面值。同时给你一个正整数 k
// 请你返回在 恰好 进行 k 次操作的前提下，你钱包里硬币面值之和 最大为多少
// 测试链接 : https://leetcode.cn/problems/maximum-value-of-k-coins-from-piles/
//n == piles.length
//        1 <= n <= 1000
//        1 <= piles[i][j] <= 105
//        1 <= k <= sum(piles[i].length) <= 2000
public class Code02_MaximumValueOfKcoinsFromPiles {


    @Test
    public void test(){
        //[[100],[100],[100],[100],[100],[100],[1,1,1,1,1,1,700]]
        //[[37,88],[51,64,65,20,95,30,26],[9,62,20],[44]]
        List<List<Integer>> p = new ArrayList<>();
        List<Integer> list1 = Arrays.asList(1,100,3);
        List<Integer> list2 = Arrays.asList(7,8,9);
        List<Integer> list3 = Arrays.asList(9,62,20);
        List<Integer> list4 = Arrays.asList(44);
        p.add(list1);
        p.add(list2);
//        p.add(list3);
//        p.add(list4);
        System.out.println(maxValueOfCoins(p, 2));
    }

    //可以转化成分组背包
    // 把k次当作条件限制，消耗是次数，value 是i次操作的值，整体分组背包
    // 将每个栈中能操作的 方案当作物品，每组每个方案只能选一个

    // dp[i][j]含义 0到i分组选取 j个硬币的最大值，也就k次操作数
    // dp[i][j] = dp[i-1][j] 不要当前组
    // 要当前组  需要遍历j前所以的情况
    // dp[i-1][j-k']+dp[i][k']
    public int maxValueOfCoins(List<List<Integer>> piles, int k) {
        int n = piles.size();
        int[][] dp = new int[n][k+1];

        for (int i = 0; i < piles.size(); i++) {

            //构建前准和
            List<Integer> groupList = piles.get(i);
            int[] preSum =  new int[groupList.size()];
            preSum[0] = groupList.get(0);
            for (int i1 = 1; i1 < groupList.size(); i1++) {
                preSum[i1] = preSum[i1-1]+groupList.get(i1);
            }
            //数组长度
            int arrLen = preSum.length;
            //构建dp
            if(i==0){
                int min = Math.min(k,arrLen);
                for (int j = 1; j <= min; j++) {
                    dp[0][j] = preSum[j-1];
                }
            }else{
                for (int j = 1; j <= k; j++) {
                    //不要
                    dp[i][j] = dp[i-1][j];
                    //要，由于j的长度可能大于数组长度 避免数组越界
                    int loopLen = Math.min(j,arrLen);
                    //遍历所有累计和等于j的情况 也就当前分组选了1，2，3，4，5 直到j个方案
                    for (int m = 1; m <= loopLen; m++) {
                        dp[i][j] = Math.max(dp[i][j],dp[i-1][j-m]+preSum[m-1]);
                    }
                }
            }
        }
        return dp[n-1][k];
    }

    public int maxValueOfCoins2(List<List<Integer>> piles, int k) {
        int n = piles.size();
        int[][] dp = new int[n+1][k+1];

        for (int i = 1; i <= piles.size(); i++) {

            //构建前准和
            List<Integer> groupList = piles.get(i-1);
            int[] preSum =  new int[groupList.size()];
            preSum[0] = groupList.get(0);
            for (int i1 = 1; i1 < groupList.size(); i1++) {
                preSum[i1] = preSum[i1-1]+groupList.get(i1);
            }
            //数组长度
            int arrLen = preSum.length;
            //构建dp
            for (int j = 1; j <= k; j++) {
                //不要
                dp[i][j] = dp[i-1][j];
                //要，由于j的长度可能大于数组长度 避免数组越界
                int loopLen = Math.min(j,arrLen);
                //遍历所有累计和等于j的情况 也就当前分组选了1，2，3，4，5 直到j个方案
                for (int m = 1; m <= loopLen; m++) {
                    dp[i][j] = Math.max(dp[i][j],dp[i-1][j-m]+preSum[m-1]);
                }
            }
        }
        return dp[n][k];
    }

}
